{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Swapping Nodes in a Linked List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #linked-list #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #链表 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: swapNodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #交换链表中的节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你链表的头节点 <code>head</code> 和一个整数 <code>k</code> 。</p>\n",
    "\n",
    "<p><strong>交换</strong> 链表正数第 <code>k</code> 个节点和倒数第 <code>k</code> 个节点的值后，返回链表的头节点（链表 <strong>从 1 开始索引</strong>）。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/01/10/linked1.jpg\" style=\"width: 722px; height: 202px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2,3,4,5], k = 2\n",
    "<strong>输出：</strong>[1,4,3,2,5]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [7,9,6,6,7,8,3,0,9,5], k = 5\n",
    "<strong>输出：</strong>[7,9,6,6,8,7,3,0,9,5]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1], k = 1\n",
    "<strong>输出：</strong>[1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2], k = 1\n",
    "<strong>输出：</strong>[2,1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2,3], k = 2\n",
    "<strong>输出：</strong>[1,2,3]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表中节点的数目是 <code>n</code></li>\n",
    "\t<li><code>1 <= k <= n <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 <= Node.val <= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [swapping-nodes-in-a-linked-list](https://leetcode.cn/problems/swapping-nodes-in-a-linked-list/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [swapping-nodes-in-a-linked-list](https://leetcode.cn/problems/swapping-nodes-in-a-linked-list/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5]\\n2', '[7,9,6,6,7,8,3,0,9,5]\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def swapNodes(self, head: ListNode, k: int) -> ListNode:\n",
    "        def f1(node):\n",
    "            if node is None:\n",
    "                return 0\n",
    "            return 1 + f1(node.next)\n",
    "        \n",
    "        sz = f1(head)\n",
    "        \n",
    "        def f2(node, k):\n",
    "            if k == 1:\n",
    "                return node\n",
    "            return f2(node.next, k - 1)\n",
    "        \n",
    "        a = f2(head, k)\n",
    "        b = f2(head, sz - k + 1)\n",
    "        \n",
    "        def swap(node1, node2):\n",
    "            tmp = node1.val\n",
    "            node1.val = node2.val\n",
    "            node2.val = tmp\n",
    "        \n",
    "        swap(a, b)\n",
    "        \n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:\n",
    "        node = pre = head\n",
    "        for _ in range(k - 1):\n",
    "            head = head.next\n",
    "        fir = head\n",
    "        while head.next:\n",
    "            pre = pre.next\n",
    "            head = head.next\n",
    "        fir.val, pre.val = pre.val, fir.val\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:\n",
    "        first, last, cur = head, head, head\n",
    "        cnt = 1\n",
    "        while cur.next:\n",
    "            if cnt < k:\n",
    "                first = first.next\n",
    "            else:\n",
    "                last = last.next\n",
    "            cur = cur.next\n",
    "            cnt += 1\n",
    "        first.val, last.val = last.val, first.val\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:\n",
    "        count = 1\n",
    "        cur = head\n",
    "        first = head\n",
    "        second = head \n",
    "        while cur.next:\n",
    "            if count < k:\n",
    "                first = first.next\n",
    "            else:\n",
    "                second = second.next\n",
    "            count += 1\n",
    "            cur = cur.next\n",
    "\n",
    "        first.val, second.val = second.val, first.val\n",
    "        return head\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:\n",
    "        left, right = head, head \n",
    "        for _ in range(k-1):\n",
    "            right = right.next \n",
    "        forward = right \n",
    "        while right.next:\n",
    "            left = left.next \n",
    "            right = right.next \n",
    "        reverse = left \n",
    "        forward.val, reverse.val = reverse.val, forward.val \n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:\n",
    "        table = []\n",
    "        cur = head\n",
    "        while cur:\n",
    "            table.append(cur)\n",
    "            cur = cur.next\n",
    "        length = len(table)\n",
    "        first_idx = k-1\n",
    "        second_idx = length - k\n",
    "        \n",
    "        temp_val = table[first_idx].val\n",
    "        table[first_idx].val = table[second_idx].val\n",
    "        table[second_idx].val = temp_val\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:\n",
    "        p0 = p1 = head\n",
    "        for _ in range(k - 1):\n",
    "            p0 = p0.next\n",
    "        temp = p0\n",
    "        while p0.next:\n",
    "            p1 = p1.next\n",
    "            p0 = p0.next\n",
    "        p1.val, temp.val = temp.val, p1.val\n",
    "        return head\n",
    "\n",
    "      "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
